package com.zs.letcode.top_interview_questions_easy.linked;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 反转链表
 * 反转一个单链表。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnnhm6/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2020/10/25 5:08 下午
 */
public class Chapter3 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        ListNode tail = new ListNode(5);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = tail;
        System.out.println(head);
        System.out.println(reverseList(head));
    }

    /**
     * 方法一：迭代
     *
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        //新链表
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            //先保存访问的节点的下一个节点，保存起来
            //留着下一步访问的
            ListNode nextNode = curr.next;
            //每次访问的原链表节点都会成为新链表的头结点，
            //其实就是把新链表挂到访问的原链表节点的
            //后面就行了
            curr.next = prev;
            //更新新链表
            prev = curr;
            //重新赋值，继续访问
            curr = nextNode;
        }
        return prev;
    }

    /**
     * 方法二：递归
     *
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        // 递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            if (this.next == null) {
                return String.valueOf(this.val);
            }
            return this.val + "->" + this.next.toString();
        }
    }

    /**
     * 1，使用栈解决
     */
    public static ListNode reverseList3(ListNode head) {
        Deque<ListNode> stack = new LinkedList<>();
        //把链表节点全部摘掉放到栈中
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        if (stack.isEmpty()) {
            return null;
        }
        ListNode node = stack.pop();
        ListNode dummy = node;
        //栈中的结点全部出栈，然后重新连成一个新的链表
        while (!stack.isEmpty()) {
            ListNode tempNode = stack.pop();
            node.next = tempNode;
            node = node.next;
        }
        //最后一个结点就是反转前的头结点，一定要让他的next
        //等于空，否则会构成环
        node.next = null;
        return dummy;
    }
}
